Global Optimality in Low-rank Matrix Optimization

摘要

This paper considers the minimization of a general objective function $f(X)$over the set of non-square $n\times m$ matrices where the optimal solution$X^\star$ is low-rank. To reduce the computational burden, we factorize thevariable $X$ into a product of two smaller matrices and optimize over these twomatrices instead of $X$. Despite the resulting nonconvexity, recent studies inmatrix completion and sensing have shown that the factored problem has nospurious local minima and obeys the so-called strict saddle property (thefunction has a directional negative curvature at all critical points but localminima). We analyze the global geometry for a general and yet well-conditionedobjective function $f(X)$ whose restricted strong convexity and restrictedstrong smoothness constants are comparable. In particular, we show that thereformulated objective function has no spurious local minima and obeys thestrict saddle property. These geometric properties implies that a number ofiterative optimization algorithms (such as gradient descent) can provably solvethe factored problem with global convergence.